The present invention relates to ATM data communications switches and switching protocols and more specifically to optimization techniques that may be used in ATM data communications switches and protocols to reduce cell size and thereby increase overall communication bandwidth.
In digital communications networks, data, packed in frames, packets or cells, is routinely transmitted over links between many nodes. The data itself is stored and communicated as a series of binary digits (bits) represented by zeros and ones. During data communications, the manner in which the bits of data are specifically arranged and the order in which they are exchanged between devices is called a protocol. Protocols are usually established by industry standards (e.g., TCP/IP, ATM, ADSL). There are many different types of protocols serving different purposes, but each typically involves sending data arranged in one specific manner, and receiving data arranged in that same manner. For example, blocks of data can be reduced in size by compression protocols that utilize standard compression algorithms before transmission from a sending node in order to conserve bandwidth. Upon reception, the blocks are decompressed to obtain the data in a useable state.
Two popular data communications protocols that have been developed to transmit data over networks are Asynchronous Transfer Mode (xe2x80x9cATMxe2x80x9d) and Asymmetric Digital Subscriber Line (xe2x80x9cADSLxe2x80x9d).
Asynchronous Transfer Mode technology is based on the efforts of the International Telecommunication Union Telecommunication Standardization Sector (ITU-T) Study Group XVIII to develop Broadband Integrated Services Digital Network (BISDN) for the high-speed transfer of voice, video, and data through public networks. ATM is capable of transferring voice, video, and data through private networks and across public networks. ATM uses very large-scale integration (VLSI) technology to segment data (for example, frames from the data link layer of the OSI reference model) at high speeds into units called cells. In a standard ATM system, each cell consists of 5 octets of header information and 48 octets of payload data. Cells transit ATM networks by passing through devices known as ATM switches, which analyze information in the header of each cell to switch that cell to the output interface that connects the switch to the next appropriate switch as the cell works its way through the network to its destination.
ATM is a cell-switching and multiplexing technology that combines the benefits of circuit switching (constant transmission delay and guaranteed capacity) with those of packet switching (flexibility and efficiency for intermittent traffic). Like X.25 and Frame Relay, ATM defines the interface between the user equipment (such as workstations and routers) and the network (referred to as the User-Network Interface, or UNI). This definition supports the use of ATM switches (and ATM switching techniques) within both public and private networks.
ADSL is a modem technology for use over twisted-pair telephone lines. ADSL can transmit more than 6 million bits per second (xe2x80x9cMbpsxe2x80x9d) to a subscriber and as much as 640 thousand bits per second (xe2x80x9cKbpsxe2x80x9d) bi-directionally. A conversation between two ADSL modems creates three information channels: a high speed downstream channel, a medium speed duplex channel and a Plain Old Telephone Service (xe2x80x9cPOTSxe2x80x9d) channel. Data rates depend upon a number of factors, including the length of the copper line, the wire gauge, the use of bridges taps and cross-coupled interference. Signal attenuation increases with line length and frequency, and decreases as wire diameter increases. The American National Standards Institute (xe2x80x9cANSIxe2x80x9d) working group T1E1.4 has approved an ASDL standard at rates up to 6.1 Mbps (ANSI Standard T1.413).
In either ATM or ADSL, connections are established between a sender and a receiver. A typical data transmission may involve the transmission of hundreds, or even thousands of cells from the sender to the receiver. A connection is basically a dedicated path through the network upon which these cells of data travel during the transmission of data from the sender to the receiver. A connection based networking scheme such as ATM thus sets-up or pre-defines a specific path between two machines within each ATM switch along the link between the two machines.
By way of example, if there are a series of ATM switches that create a network path between a sending and receiving host, as the first cell of a stream of data enters the network, the first ATM switch will determine the most appropriate xe2x80x9cnext switchxe2x80x9d to which that cell should be switched. The first switch then creates a connection within itself (i.e., using software to configure the switches switching hardware) for future cells destined for the receiver. As the first cell makes its way to each successive ATM switch, each switch sets-up its own connection for cells between the sender and receiver. Once the first cell has made it to the receiver, subsequent cells may be quickly switched using the pre-established connections which remain configured until the sender and receiver no longer need to communicate. To switch each cell, the header portion of the cell is used to determine which connection is associated with the cell and therefore which port the cell should be switched to. When the connection (i.e., the communication session) is over and there are no more cells to be transmitted, each ATM switch can take-down its connections.
Though ATM cells are only 53 bytes in length, prior art systems have been developed to decrease the transmitted cell size to increase overall network bandwidth. U.S. Pat. No. 5,414,701, entitled xe2x80x9cMethod and data structure for performing address compression in an asynchronous transfer mode (ATM) systemxe2x80x9d, discloses a system which uses address compression in an ATM cell. In this system, before transmission of the cell, the address is compressed and replaced by a virtual path identifier referred to as a link. The link is computed based on the address and header information and is shorter in length than the overall header. Once the cell is transmitted and as it traverses the network, each switch that encounters the cell looks up the link appended to the cell in a link table maintained at the switch. The link table indicates the eventual destination for that cell, based on the cells unique link. As such, the switch can direct the cell in the appropriate direction. Essentially, before transmission, a link is appended to each cell based on a computation derived form the original cell header information. There may be a number of different links in use within a network, each signifying a specific connection (i.e., source and destination communication session).
Various problems are inherent in systems for reducing header information within cells transmitted on a network, such as those systems noted above. Existing systems and devices for processing ATM cells must transmit header information (including addressing and/or link information) with every ATM cell sent. In normal ATM systems, this header information creates significant overhead. Specifically, five bytes of header are sent for every 48 bytes of data sent in a standard ATM cell, and at least a link must be appended to each cell in the address compression mode noted above. Moreover, using the link mechanism for address compression requires a complex calculation to be made for each cell. The cell header must be matched to any one of a number of existing links, and then the header must be replaced by the matching link. If a link does not yet exist for the header of a current cell, a new link must be created and propagated throughout the switching network. Each switch must also maintain up-to-date link tables in order for throughput to remain efficient.
In all cases of prior art cell switching systems, cell header overhead reduces the bandwidth available over a given link thus reducing the amount of data and/or number of users that can avail themselves of a given link. Over serial links (e.g., ADSL) this often reduces the effective reach for a given data rate. Often the full cell headers and the token-based cell headers contain identical addressing or token information. Thus, for a connection that uses thousands of cells during a single session, the header or token overhead can become quite substantial.
The present invention detects situations in which redundant header or cell information would be sent by comparing information in an instant cell with stored information from a previous cell, and eliminates the redundant information (optimization). Preferably, redundant information is all or some portions of the header of a stream of cells. The receiving end of the transmission detects arrival of an optimized (i.e., reduced size) cell either by performing a calculation on incoming data and/or by examining a portion of the cell against a previously saved portion of the cell. If the calculation produces a matching result, or if a received header value is not equal (i.e., is not equivalent in value) to a saved header value from a former cell, then the cell is a full sized (i.e., un-optimized) cell. In one embodiment, instead of a calculation, a header field used for Header Error Control (HEC) is used as the header value in a comparison and the Header Error Control field is compared with a saved Header Error Control field from a former cell that was previously received. If the calculation produces a non-matching result or if the Header Error Control field is the same as a formerly saved Header Error Control field, the cell is an optimized cell and thus is shorter in length (i.e., number of bits transmitted which constitute the cell) and a formerly saved complete header is appended to the cell, thus returning the optimized cell to a cell of a standard size.
In one embodiment, an unoptimized (i.e., standard sized) cell size is 53 bytes and an optimized cell is transmitted without a standard five byte header (which includes the Header Error Control field as one of the five header bytes) and is thus 48 bytes in size. Upon reception of an optimized headerless cell, the header (5 bytes) of a formerly received cell will be appended to the 48 byte cell transmitted to re-create a normal 53 byte cell. To detect that the incoming optimized cell bytes do not have a header, a calculation is done that determines if the first few bytes received (e.g. the first five) are representative of a standard cell header or not. If not, then it is assumed the cell being received is an optimized cell.
The present invention overcomes the problems in the prior art by increasing the bandwidth of a link without significantly adding to the processing cost of transmitting that data. The optimization system of the invention, by saving and eliminating redundant data, is very efficient and cost effective to implement. The implicit signaling that an optimized cell is present (by examining the bytes of data which make up a cell and using either the calculation or detection of a shortened header) is an elegant way to communicate information without the overhead of adding additional data in the form of a full sized header to the transmission.
Compatibility with existing data communications devices and techniques is achieved by way of industry standard handshaking. That handshaking allows the invention to be implemented in devices that can communicate with devices that recognize standard ATM or other data communications formats as well as those that do not.
According to one aspect of the invention a method and apparatus for propagating a data stream of cells is provided. In operation, upon transmission of a cell, a first portion of a cell of the data stream is compared against a previously saved first portion of a former cell of the data stream. The first portion is preferably a header portion, or alternatively, the first portion can be the entire header, or certain fields of the header, or just one field. An optimized second portion of the cell of the data stream is then transmitted if the previously saved first portion of the former cell of the data stream equals the first portion of the cell of the data stream, without disrupting a sequence of cells of the data stream. Preferably, the optimized second portion is the data field of the cell. The optimized second portion of the cell of the data stream is smaller in size than an entire portion of the cell of the data stream. That is, the entire portion is the header fields and data field, while the optimized second portion is either the data field only or the data field and a shorten header. Thus the selective transmission of either the entire portion of the optimized second portion is done at the transmitting device. The system then saves the first portion of the cell of the data stream if the previously saved first portion of a former cell of the data stream does not equal the first portion of the cell of the data stream. Then, an entire portion of the cell of the data stream is transmitted and the saving process results in a new saved first portion of a cell of the data stream. That is, if the next cell to be transmitted is different than a former cell, the header of the next cell is saved as a new first portion.
Thus, if two or more consecutive cell headers are the same, in one embodiment, only the payload or data portion of the cells is transmitted and is referred to herein as an optimized cell. If a cell (i.e., next cell in a stream) to be transmitted is different (i.e., has different header information), its header is saved and it is transmitted in full as an entire cell so the receiver can also save its header. Then, as subsequent cells are transmitted, if their headers are all the same as the most recent saved header, only their payloads are sent. The receiver can do data checks on the receiver payload-only cell to determine if it is an optimized payload-only cell or if it is a full sized cell. These data checks are the calculations and header field comparisons noted above. Optimized cells then have the saved header appended to them at the receiving end and are passed on for further processing.
In an alternative embodiment, instead of transmitting absolutely no header information, the data or payload field of a cell is sent along with only the header error correction field of the original cell header. Thus, the optimized cell is 49 bytes, with 48 bytes being used for the data or payload field and the 49th byte being the HEC field. This is more advantageous than prior art systems which optimize cell lengths by using specially calculated tokens as shortened headers since in this invention, no token must be computed as the HEC is readily available from the header itself.
In alternative embodiments, there may be more than one saved header portion as determined by a number of simultaneous connections. This would be the case where many connections are multiplexed through a common transmitter. Thus, a stream of cells destined for one host (and thus having common header information) can be stripped of their headers as they are sent, and also, one or more other streams of cells can have header information stripped as well, assuming the cells in each stream have common header information, respectively per stream. In other words, the basic principles of the invention are expanded in alternative embodiments to cover more than one stream of cells to be transmitted as optimized cells. The only difference is that the transmitter of multiple optimized streams must keep a copy of the header portions of the most recently sent cells for each stream in which cells having a common header are transmitted.
In another embodiment of the invention, a computer program product is provided. The computer program product may be any type of computer readable object such as a disk or tape. The computer program product has a computer-readable medium including computer program logic encoded thereon for receiving an optimized data stream of cells. The computer program, when executed on a computer processor, causes the processor to perform the steps of receiving a portion of a cell and determining, based on the portion of the cell, if the cell is associated with a formerly received cell. If so, the computer logic appends a formerly saved portion of a formerly received cell to the cell, and if not, saves a portion of the cell as a saved portion. The cell is then subjected to further processing.
The present invention overcomes the aforementioned prior art problems of achieving optimal bandwidth over communications links by reducing the amount of redundant data being sent over those links.